You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.
You are restricted with the following rules:
- The division operator
'/'represents real division, not integer division.- For example,
4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
- For example,
- Every operation done is between two numbers. In particular, we cannot use
'-'as a unary operator.- For example, if
cards = [1, 1, 1, 1], the expression"-1 - 1 - 1 - 1"is not allowed.
- For example, if
- You cannot concatenate numbers together
- For example, if
cards = [1, 2, 1, 2], the expression"12 + 12"is not valid.
- For example, if
Return true if you can get such expression that evaluates to 24, and false otherwise.
Input: cards = [4,1,8,7] Output: true Explanation: (8-4) * (7-1) = 24
Input: cards = [1,2,1,2] Output: false
cards.length == 41 <= cards[i] <= 9
fromfunctoolsimportcachefromitertoolsimportpermutationsfrommathimportgcdclassSolution: @cachedefadd(self, a: (int, int), b: (int, int)) -> (int, int): lcm=abs(a[1] *b[1]) //gcd(a[1], b[1]) return (a[0] *lcm//a[1] +b[0] *lcm//b[1], lcm) @cachedefsub(self, a: (int, int), b: (int, int)) -> (int, int): returnself.add(a, (-b[0], b[1])) @cachedefmul(self, a: (int, int), b: (int, int)) -> (int, int): return (a[0] *b[0], a[1] *b[1]) @cachedefdiv(self, a: (int, int), b: (int, int)) -> (int, int): ifb[0] ==0: return (0, 1) returnself.mul(a, (b[1], b[0])) @cachedefjudge1(self, a: (int, int)) ->bool: returna[0] %a[1] ==0anda[0] //a[1] ==24@cachedefjudge2(self, a: (int, int), b: (int, int)) ->bool: returnself.judge1(self.add(a, b)) orself.judge1(self.sub(a, b)) orself.judge1(self.mul(a, b)) orself.judge1(self.div(a, b)) @cachedefjudge3(self, a: (int, int), b: (int, int), c: (int, int)) ->bool: returnself.judge2(self.add(a, b), c) orself.judge2(self.sub(a, b), c) orself.judge2(self.mul(a, b), c) orself.judge2(self.div(a, b), c) or \ self.judge2(a, self.add(b, c)) orself.judge2(a, self.sub(b, c)) orself.judge2( a, self.mul(b, c)) orself.judge2(a, self.div(b, c)) @cachedefjudge4(self, a: (int, int), b: (int, int), c: (int, int), d: (int, int)) ->bool: returnself.judge3(self.add(a, b), c, d) orself.judge3(self.sub(a, b), c, d) orself.judge3(self.mul(a, b), c, d) orself.judge3(self.div(a, b), c, d) or \ self.judge3(a, self.add(b, c), d) orself.judge3(a, self.sub(b, c), d) orself.judge3(a, self.mul(b, c), d) orself.judge3(a, self.div(b, c), d) or \ self.judge3(a, b, self.add(c, d)) orself.judge3(a, b, self.sub( c, d)) orself.judge3(a, b, self.mul(c, d)) orself.judge3(a, b, self.div(c, d)) defjudgePoint24(self, cards: List[int]) ->bool: for (a, b, c, d) inpermutations(cards): ifself.judge4((a, 1), (b, 1), (c, 1), (d, 1)): returnTruereturnFalse